Many storage systems generally require some form of redundancy to achieve fault tolerance. One possible approach to provide fault tolerance is by storing full size replicas of data blocks on independent units of failure. This method provides the highest degree of availability because it does not require reading from more than one storage location or data re-computation on failure. However, this approach is also very expensive because the space taken up by full size replicas is equal to the amount of user data per each added degree of fault tolerance.
Another possible approach is to implement erasure coding, which takes advantage of the fact that there are usually more available independent units of failure than the desired degree of fault tolerance. A common example of erasure coding in storage is known as RAID 4 (redundant array of independent disks level 4), where the results of performing an exclusive OR operation on data blocks are stored on all disks except that the parity disk is stored on the parity disk. In the event of a single disk failure, the lost data block is computed as the exclusive OR of all available data blocks, including the parity block. The amount of redundant data needed by RAID 4 is equal to 1/N of the amount of user data where N is an arbitrarily chosen number that is less than the number of independent disks. For example, if four disks are available in the system, the amount of redundant data needed for protection against one disk failure is equal to ⅓ of the amount of user data.
With erasure coding, it is much more expensive to assure protection against multiple disk failures with the conventional techniques. RAID 6 refers to a system that protects against at most two hardware failures at the expense of extra 2/N times the amount of user data. It is generally true that protecting again K hardware failures requires K/N extra space in an array of independent disks. The Reed-Solomon scheme corresponds to a class of erasure coding algorithms that can be used to protect against multi-disk failures. The problem is that these algorithms are very complicated to implement, require a significant number of operations to be performed, and are not very efficient either in terms of storage or the process to perform recovery after a failure.
Therefore, there is a need for an improved approach to implement erasure coding for storage systems that can address multiple failures.